package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/8 15:07
 *
 *
 最小k个数：堆排序，优先队列
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main16 {


    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer>ans=new ArrayList<>();
        if(input==null||input.length==0||k==0)return ans;

        PriorityQueue<Integer>queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //对于compareTo，如果o1<o2返回-1，相等返回0，o1>o2返回1
                //o2<o1，表示队头最大是大根堆
                return o2.compareTo(o1);
            }
        });
        //堆大小为k
        for(int i=0;i<k;++i){
            queue.offer(input[i]);
        }
        //维护这个堆
        for(int i=k;i<input.length;++i){
            //较小元素入堆,堆顶为最大元素
            if (input[i]<queue.peek()){
                queue.poll();
                queue.offer(input[i]);
            }
        }
        for(int i=0;i<k;++i){
            ans.add(queue.poll());
        }
        return ans;
    }
    public static void main(String[] args) {
        Main16 main16=new Main16();
        int inp[]={4,5,1,6,2,7,3,8};
        System.out.println(main16.GetLeastNumbers_Solution(inp,4));
    }
}
